package main

import (
	"fmt"
	"math"
)

func main() {
	fmt.Println(maxScoreSightseeingPair1([]int{8, 1, 5, 2, 6}))
}

func maxScoreSightseeingPair(values []int) int {
	max := math.MinInt
	for i := 0; i < len(values); i++ {
		for j := i + 1; j < len(values); j++ {
			if max < values[j]+values[i]+i-j {
				max = values[j] + values[i] + i - j
			}
		}
	}
	return max
}

func maxScoreSightseeingPair1(values []int) int {
	maxPrev := values[0]
	maxSum := math.MinInt
	for i := 1; i < len(values); i++ {
		if sum := values[i-1] + i - 1; maxPrev < sum {
			maxPrev = sum
		}
		if maxSum < maxPrev+values[i]-i {
			maxSum = maxPrev + values[i] - i
		}
	}
	return maxSum
}
